package lc.回溯;

import java.util.ArrayList;
import java.util.List;

/**
 * @description:
 * @author: qian
 * @createDate: 2021/10/5
 */
public class n皇后 {

    int[] cols;
    List<List<String>> list = new ArrayList<>();
    public List<List<String>> solveNQueens(int n) {
        cols = new int[n];
        place(0,n);
        return list;
    }
    public void place(int row,int n) {
        if (row == n) {
            printQueens(cols,n);
            return;
        }
        for (int col = 0; col < n;col++) {
            if (isOK(row,col,n)) {
                cols[row] = col;
                place(row + 1,n);
            }
        }
    }
    public boolean isOK(int row,int col,int n) {

        for (int i = 0; i < row; i++) {
            if (cols[i] == col) return false;
            if (row - i == Math.abs(col - cols[i])) return false;
        }
        return true;
    }
    private void printQueens(int[] result,int n) {
        List<String> arr =  new ArrayList<String>();
        for (int row = 0; row < n; ++row) {
            StringBuffer s = new StringBuffer();
            for (int column = 0; column < n; ++column) {
                if (cols[row] == column)
                    s.append("Q");
                else
                    s.append(".");
            }
            arr.add(s.toString());
        }
        list.add(arr);
    }
}
